\documentclass[]{article}

\input{../framework/sp}
\splanguage{french}

\title{Grand concours du meilleur algorithme}
\author{Maxime \tsc{Gaudin} \& Melissa \tsc{Mongeau}.}

\newtheorem{constraint}{Contrainte}
\labelformat{constraint}{C.#1}

\begin{document}
\maketitle

\begin{abstract}
Ce projet nous permet, au travers d'un problème ``grandeur nature'' de mettre
en œuvre l'ensemble des techniques de conception d'algorithme étudiées en cours
ainsi que notre capacité à raisonner sur des problèmes plus complexes que ceux
que nous avons pu aborder jusqu'à maintenant. 
\end{abstract}

\section{Résumé de la problématique}
Dans le cadre d'un évènement, il est fréquent que de nombreux temps morts
jonchent le travail de tous les intervenant. Ces temps morts sont donc payés
mais pas exploités. Il s'agit ici de les minimiser afin de réduire au maximum
le cout de l'événement.

Pour cela, nous devons faire face aux contraintes suivantes :

\begin{constraint}\label{cdim}
  Nous ne disposons d'aucune information quant au dimensionnement du
    problème (\eg le nombre de musiciens, de pièces, \etc).
\end{constraint}

\begin{constraint}\label{ctime}
  Nous disposons d'un temps limité (et relativement court)\footnote{300
  secondes.} pour le calcul.
\end{constraint}

\begin{constraint}\label{cproc}
  Nous disposons de machine mono-processeur ou au mieux, bi-processeur.
\end{constraint}

\begin{constraint}\label{chd}
  Nous disposons de machines muni d'un disque dur magnétique avec un
  temps de latence supposé grand (\eg à cause du réseau).
\end{constraint}

\section{Élaboration de l'algorithme}
Il s'agit déjà d'éliminer les patrons d'algorithmes qui ne peuvent pas
s'appliquer au problème.

\subsection{Recherche de patrons de conception}
\paragraph{\tackmark{} Énumération des solutions}
Les contraintes \ref{cdim} \& \ref{ctime} nous empêchent de l'envisager.
En effet, la complexité de tels algorithmes est de l'ordre de $O(2^n)$ où $n$
est le nombre de pièces du concert. Par conséquent, un concert à plus d'un
vingtaine de pièces excède déjà nos capacités de calcul.

\paragraph{\tuckmark{} Énumération des solutions avec \tsl{pruning} systématique
(\tsl{Branch \& bound})}
Bien que cette solution soit déjà plus envisageable, il est très difficile de
trouver des fonctions de sous-estimation (\resp surestimation) des solutions
partielles. Ces questions demeurent cependant un problème intéressant.

\paragraph{\tackmark{} Programmation dynamique}
La difficulté de ce problème vient notamment du fait que les sous-problèmes ne
sont pas beaucoup plus simples à résoudre que l'instance complète. De plus, les
contraintes \ref{cdim} et \ref{chd} contre-indiquent cette solution. En,
effet, dans le cas de grandes instances, notre programme serait amené à
\gls{swapper} ce qui dégraderait considérablement les performances de notre
programme.

\paragraph{\tackmark{} Diviser-pour-régner}
L'approche diviser pour régner est, dans ce cas, une très mauvaise approche.
En effet, s'il est facile de diviser la taille du problème et de les résoudre
pour une instance à deux pièces, trouver une combinaison optimale relève du
défi (si tant est qu'il existe une méthode de combinaison optimale)\footnote{À
priori non puisque le problème est au moins NP-dur.}.

Aussi, le multi-threading est proscrit à cause de la contrainte \ref{cproc}.

\paragraph{\tickmark{} Heuristique gloutonne}
L'heuristique gloutonne reste, à nos yeux, une des solutions les plus
praticable. Hélas, nous ne disposons d'aucune garantie quant à la qualité du
résultat.

\subsection{Piste de recherche}
Après cette analyse succincte des possibilités qui s'offrent à nous, il est
d'ors et déjà possible d'en déduire quelques pistes de recherche :
\begin{itemize}
  \item Glouton nous fournis une solution quelque soit le temps imparti.
  \item Une méthode de raffinement itératif de la solution serait idéal dans
    les conditions du problème (temps limité, instance de taille inconnue)
\end{itemize}

Enfin, il est important de garder en tête que ce genre de problème est
NP-complet et qu'il n'existe aucun algorithme qui permette, sur une machine
déterministe, de trouver la solution optimale en temps polynomiale.

\section{Description de l'algorithme} 
L'algorithme procède en 2 étapes :
\begin{enumerate}
  \item Fournir quelques solutions que l'on sait ``pas trop mauvaises'' grâce à
    un algorithme glouton.
  \item Tester des mélanges aléatoires de ces solutions afin de profiter du
    temps restant pour améliorer la solution.
\end{enumerate}

\subsection{Procédure gloutonne}
Comme le montre \ref{greedyalg}, l'algorithme glouton possède deux subtilités :
\begin{enumerate}
  \item Il utilise le ``classement'' des musiciens pour faire son choix
    glouton. Il faut donc établir une (ou plusieurs) heuristique permettant de
    proposer une valeur pour chaque musicien en fonctions des différents
    paramètres dont nous disposons (\cf \tsl{section \ref{heuristics}}).
  \item L'ordre des pièces du musicien précédent est changé afin d'améliorer
    le coût du musicien courant sans pour autant dégrader le sien 
    (\tsl{ligne \ref{swap}}).
\end{enumerate}

\begin{algorithm}
  \SetKwInOut{Input}{Entrée}
  \SetKwInOut{Output}{Sortie}

  \Input{Une heuristique de tri, une liste de musiciens.}
  \Output{La liste ordonnée des pièces à jouer.}
  ~\\

  \ttt{schedules} := Un tableau de liste de pièce (Une liste pour chaque
    musicien) \;
  \ttt{musiciens} := Ensemble des musiciens triés en fonction de
    l'heuristique passée en paramètre \;
  ~\\
  \ForEach{Musicien de la \ttt{musiciens}}{
    \ForEach{Pièce jouée par ce Musicien}{
      \If{La pièce a été jouée avant lui}{
        \eIf{La pièce a été jouée par le musicien avant lui}{
          Déplacer la pièce pour la mettre à la fin de la liste du
          musicien précédent\label{swap} \;
        }
        {
          Ajouter la pièce à sa liste \;
        }
      }
    }
  }

  Retourner la fusion des listes des musiciens \;
\caption{Procédure gloutonne modifiée\label{greedyalg}}
\end{algorithm}

\subsection{Heuristiques\label{heuristics}}
\paragraph{Heuristique 1}
:es musiciens sont classé en fonction du temps qu'ils passent à ne pas jouer
et de leur salaire. L'idée étant de prioriser ceux qui ne jouent pas beaucoup
de pièces où ceux qui ne jouent pas les pièces qui sont longues afin qu'ils
attendent le moins possible entre leurs pièces. 

Nous multiplions ce temps par le salaire horaire du musicien afin que ceux qui
coutent le plus cher soit ``avantagés''.

\paragraph{Heuristique 2}
Dans cette heuristique, l'idée est d'essayer d'établir un coût en fonction du
nombre de pièce à jouer et du taux horaire du musicien. Pour cela, nous avons
utilisé une ``constante magique'' qui après de nombreux tests, semble une
bonne approximation du ration temps payé / temps joué.

\paragraph{Heuristique 3}
Cette heuristique tient uniquement compte du coût du musicien pour les classer. 

\section{Utilisation du programme}
\subsection{Compilation}
Dans le répertoire racine :
\begin{verbatim}
./configure
make
\end{verbatim}

\subsection{Exécution}
\begin{verbatim}
./pantoute dataset1.dat 300
\end{verbatim}

\newpage
\section{Conclusion}
Si en pratique (et sur les jeux de tests) l'algorithme semble donner de bon
résultats, il ne fournit aucune garantie et ne pourrais donc pas être mis en
place dans un contexte industriel.

\vfill
\tableofcontents
\end{document}

